import rand

def new(data):
    h = []
    tag = 1
    h.append(tag)
    while tag < len(data)//3:
        tag = 3*tag+1
        h.append(tag)
    return h

def two(data):
    h = []
    tag = len(data)
    while tag != 1:
        tag = tag>>1
        h.append(tag)
    return h

@rand.stime
def heer(data, reverse=True):
    if reverse==True:
        h = new(data)
    if reverse==False:
        h = two(data)
    for n in h[::-1]:
        for i in range(n, len(data)):
            j = i
            while True:
                if j < n:
                    break
                if reverse==True:
                    if data[j] > data[j-n]:
                        data[j], data[j-n] = data[j-n], data[j]
                else:
                    if data[j] < data[j-n]:
                        data[j], data[j-n] = data[j-n], data[j]
                j -= n
    return data

if __name__ == "__main__":
    data = rand.rand(0, 100000, 10000)
    data1 = heer(data, reverse=False)
